package com.sakura.二叉树;

public class Code98_验证二叉搜索树 {

    private long pre = Long.MIN_VALUE;
  
    // Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        Code98_验证二叉搜索树 code = new Code98_验证二叉搜索树();
        TreeNode root = new Code98_验证二叉搜索树().new TreeNode(5);
        root.left = new Code98_验证二叉搜索树().new TreeNode(1);
        root.right = new Code98_验证二叉搜索树().new TreeNode(4);
        root.right.left = new Code98_验证二叉搜索树().new TreeNode(3);
        root.right.right = new Code98_验证二叉搜索树().new TreeNode(6);
        System.out.println(code.isValidBST_post(root));
    }

    // 中序
    public boolean isValidBST_inorder(TreeNode root) {
        if (root == null) return true;

        boolean left = isValidBST_inorder(root.left);
        if (!left) {
            return false;
        }

        if (root.val <= pre) {
            return false;
        }
        pre = root.val;

        return isValidBST_inorder(root.right);
    }

    public boolean isValidBST_post(TreeNode root) {
        return dfs(root)[1] != Long.MAX_VALUE;
    }

    private long[] dfs(TreeNode node) {
        if (node == null) {
            return new long[]{Long.MAX_VALUE, Long.MIN_VALUE};
        }
        long[] left = dfs(node.left);
        long[] right = dfs(node.right);
        long x = node.val;
        // 也可以在递归完左子树之后立刻判断，如果发现不是二叉搜索树，就不用递归右子树了
        if (x <= left[1] || x >= right[0]) {
            return new long[]{Long.MIN_VALUE, Long.MAX_VALUE};
        }
        return new long[]{Math.min(left[0], x), Math.max(right[1], x)};
    }

//    作者：灵茶山艾府
//    链接：https://leetcode.cn/problems/validate-binary-search-tree/solutions/2020306/qian-xu-zhong-xu-hou-xu-san-chong-fang-f-yxvh/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
